The invention relates generally to data networks. More specifically, the invention relates to providing a guaranteed quality of service for connections in a packet-switched network.
In communications technology, there is an ever-increasing demand for high-performance networks. This increased demand has led to the development of improved networks capable of handling larger volumes of data with smaller delays.
Communications networks, such as ATM networks or the Internet, are generally formed with a number of transmission links interconnected with switches. A transmission link is any medium through which signals are communicated and can be single or multiple twisted pairs, optical fiber, coaxial cable, radio links, or other mediums. A switch is a device with one or more input ports and one or more output ports. The switch directs bits arriving at an input port to the appropriate output port. Switching in communications is accomplished using one of two methods: circuit switching and packet switching. Only packet switching is relevant for the purposes of the present discussion.
In packet switching, the data in a data stream is divided into xe2x80x9cpackets.xe2x80x9d In addition to a portion of data, each packet carries various identifying information about the data. Such identifying information includes routing information, for instance, source and destination addresses for the data. When a packet arrives at a switch, it is stored in a buffer. The switch looks at the routing information in the packet and routes the packet to the appropriate output port. The packets are then forwarded one xe2x80x9chopxe2x80x9d (or switch) at a time, until they reach their destination.
Generally in packet switching, each packet in a particular data stream does not necessarily follow the same path to its destination as the others. Nonetheless, certain types of packet switching, e.g., ATM, do specify the path that the packets are to follow between the switches for a particular end-to-end connection. Such a predetermined path is typically referred to as a xe2x80x9cvirtual channelxe2x80x9d or xe2x80x9cvirtual connection.xe2x80x9d
Unlike general packet switching where packets are not guaranteed to arrive in the order they were sent, when virtual channels are specified, all of the packets follow the same route along the virtual channel, thereby guaranteeing the order of arrival. These xe2x80x9cvirtual connectionsxe2x80x9d have greatly enhanced the performance of networks in using resources efficiently and can often provide a minimum xe2x80x9cquality of servicexe2x80x9d. xe2x80x9cQuality of servicexe2x80x9d generally refers to guaranteed bounds on the delay, loss rate, available throughput, and/or other measures of performance.
As the applications of data transmission mature, the need for guaranteed quality of service is increasing. Several networks have attempted to provide a guaranteed quality of service. For instance, Asynchronous Transfer Mode (ATM) networks provide guaranteed bandwidth, loss rate, and delays for each virtual connection. To do so, ATM networks utilize (1) traffic policing, and (2) connection admission. In one type of ATM service, variable bit ratexe2x80x94real time (VBR-rt), traffic policing is carried out at the network switches, which set aside sufficient buffer space to absorb the traffic bursts and sufficient transmission rate to accommodate the average rate of traffic through the switch based on values provided by the connection request. A connection admission controller assures that no connection is admitted when the network switches have insufficient non-committed buffer space and transmission rate to carry the requested connection. In this manner, VBR-rt ATM can guarantee performance within the parameters defined by peak rate, average rate, and burst size. Other types of networks, such as Frame Relay, can provide similar guarantees.
Although ATM provides certain guarantees on quality of service, this protocol generally depends upon a fully operational network. For instance, if any part of a virtual connection in an ATM network fails, the entire virtual connection will fail and a new virtual connection will need to be established. While the new virtual connection may provide guarantees of quality of service, these guarantees may not reach the same standards as those of the original virtual connection. Therefore, in some versions of ATM, to accommodate a link failure, two paths are set up for each connection instead of one: a normal path and a backup path in case the normal path fails. Data is sent on both virtual paths simultaneously. If the normal path fails, then the data stream from the backup path is used. Otherwise, the data from the backup path is ignored.
Another method of providing more reliable transmission services in the event of a network failure and similar to that described for ATM is utilized in Synchronous Optical Network (SONET). SONET transmission links are typically arranged in dual rings that interconnect the switches. Between any two switches on the rings there are two disjoint paths: one clockwise path and one counterclockwise path. SONET sends every bit stream from its source switch to its destination switch simultaneously on each path. The destination switch monitors the two copies of the bit stream and uses one stream by default. If the default stream fails, e.g., as a result of a fault along its path, the destination switch uses the alternate copy of the bit stream.
Although both SONET and ATM provide systems where transmissions are robust against failures on the rings, they are both also very wasteful of valuable resources. In SONET, the resources used to support the backup paths cannot be used by other connections, even when there is no network failure. In ATM, these resources cannot be committed to other connections.
Another type of network protocol that attempts to guarantee quality of service is the Internet Protocol (IP). Although originally designed as a xe2x80x9cbest effortxe2x80x9d protocol without guarantees, and without using virtual connections, several variations have been developed that provide more control over packet delivery. One such variation is referred to as xe2x80x9cdifferentiated servicesxe2x80x9d or DiffServ. Another variation is xe2x80x9cmultiprotocol label switchingxe2x80x9d or MPLS. Both of these variations use scheduling algorithms at the switches (routers) that allocate different fractions of the available transmission rate to various queues. Packets are placed in predetermined queues in accordance with information carried in each packet. The queues are multiplexed according to the scheduling algorithm. When performed properly, the scheduling algorithm places packets on the transmission line from each queue to provide a guaranteed transmission rate for the queue.
Even in xe2x80x9cbest effortxe2x80x9d form, IP networks are inherently reliable. IP accommodates link failures by updating routing tables in the switches. Periodically, e.g., every few seconds, the switches exchange information about their preferred paths to destinations. As a failure occurs, the information regarding the failure gets propagated through this exchange mechanism. Hence, the network can automatically adapt to any network failures. Nonetheless, this propagation and re-routing exchange takes considerable time and is not suitable for real-time applications.
A system and method in accordance with the invention overcomes the deficiencies as described above and provides a system that efficiently allocates resources while providing reliable and guaranteed quality of service. Such a system is generally used in a network that includes a plurality of nodes and a plurality of links interconnecting the nodes. In accordance with an embodiment of the invention, for each connection i in the network established between a pair of nodes, a normal path ni between the nodes having a rate Ni is established and an alternate, or backup, path bi having a rate Bi is established.
For each link comprising a normal path ni, the system maintains information as to the resources utilized by the connections. For instance, in one embodiment of the invention, the system tracks the bandwidth A(j) reserved for connections carried on each link j in the absence of network failures using the equation       A    ⁡          (      j      )        =            ∑      i        ⁢                  N        i            ⁢      1      ⁢                        {                      j            ∈                          n              i                                }                .            
The system further tracks the bandwidth reserved on each link j in the event of a network failure f using the equation       A    ⁡          (              j        ;        f            )        =                    ∑        i            ⁢                        N          i                ⁢        1        ⁢                  {                      j            ∈                                          n                i                            ⁢                              xe2x80x83                            ⁢              and              ⁢                              xe2x80x83                            ⁢              f                        ∉                          n              i                                }                      +                  ∑        i            ⁢                        B          i                ⁢        1        ⁢                              {                          j              ∈                                                b                  i                                ⁢                                  xe2x80x83                                ⁢                and                ⁢                                  xe2x80x83                                ⁢                f                            ∉                                                b                  i                                ⁢                                  xe2x80x83                                ⁢                and                ⁢                                  xe2x80x83                                ⁢                f                            ∈                              n                i                                      }                    .                    
Information is transmitted for each connection over the designated normal path, and not the backup path, until a failure occurs on the normal path. Once a failure occurs, then the connection is rerouted over its backup path.
Upon receipt of a new connection request, a system in accordance with the invention selects a potential normal path and backup path for the new connection and then evaluates whether adequate resources are available on the selected path to support the new connection. To perform such evaluation, the system will update the values of A(j) and A(j;f) to account for the new connection and then determine if the resources available on any particular link or node are exceeded. If exceeded, the connection is rejected and the quantities of A(j) and A(j;f) are returned to their original values.
One embodiment of the invention can additionally accommodate an event in which there are more than two paths (e.g., a normal path and a backup path) for a given connection, for instance a network that is doubly-attached to the Internet. In such a network, packets destined for the same node may arrive at either of the two nodes attaching the network to the Internet. At each attachment node, a normal path and a backup path may be established. If there is more than minimal overlap among the links and nodes of any two of the paths, then, in accordance with an embodiment of the invention, only one queue is designated in the overlapping nodes to accommodate the overlapping paths. Thus, network resources are used efficiently.